class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        //希尔排序 5 2 3 1
        for(int d=nums.size()/2;d>0;d/=2){//2,1,0
            for(int i=d;i<nums.size();i++){
                for(int j=i-d;j>=0;j-=d){
                    if(nums[j]>nums[j+d]){
                        swap(nums[j+d],nums[j]);
                    }
                }
            }
        }
        return nums;
    }
};